package com.zjj.lbw.interview.tree;

import com.zjj.lbw.interview.common.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhanglei.zjj
 * @description 二叉树-最小深度 深度优先/广度优先
 * 给定一个二叉树，找出其最小深度。
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 * @date 2023/9/2 18:26
 */
public class BinaryTreeMinDepth {
    /**
     * 深度优先
     * @param root
     * @return
     */
    public static int minDepth1(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int minDepth = Integer.MAX_VALUE;
        // 如果某个节点 左、右子节点都为null，说明遍历到了叶子节点
        if (root.left == null && root.right ==  null) {
            return 1;
        }
        if (root.left != null) {
            minDepth = Math.min(minDepth1(root.left), minDepth);
        }
        if (root.right != null) {
            minDepth = Math.min(minDepth1(root.right), minDepth);
        }

        return minDepth + 1;
    }

    /**
     * 基于广度优先
     * @param root
     * @return
     */
    public static int minDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 根节点深度为1
        root.depth = 1;

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            // 只要遍历到任何一个叶子节点，就说明找到了最小深度
            if (node.left == null && node.right == null) {
                return node.depth;
            }
            int depth = node.depth;
            if (node.left != null) {
                node.left.depth = depth + 1;
                // 因为广度优先，需要先处理右节点，因此当前左节点的子节点需要处理完但当前节点右节点之后再处理，
                // 需要把当前节点左节点先暂存到队列
                queue.offer(node.left);
            }
            if (node.right != null) {
                node.right.depth = depth + 1;
                queue.offer(node.right);
            }
        }

        return 0;
    }

    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(7, null, null);
        TreeNode node6 = new TreeNode(6, node7, null);
        TreeNode node5 = new TreeNode(5, null, null);
        TreeNode node4 = new TreeNode(4, null, null);
        TreeNode node3 = new TreeNode(3, node6, null);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);

        System.out.println(minDepth1(node1));
        System.out.println(minDepth2(node1));
    }
}
